The present invention relates to specialized electronic devices for looking up data, such as may be used in high-speed network routers and switches and, in particular, to a device that may optimize its memory topology for different lookup tasks.
Computer networks allow the exchange of data among spatially separated computers connected by “links”, the latter physically implemented as electrical conductors, fiber optics, and radio waves. The dominant network protocols work by dividing a data message into data packets, each of which contains a destination address. The destination address attached to the packets permits the packets to navigate through complex and dynamically changing networks to the destination. When particular links used by a message become crowded or disabled, packets of that message, guided by the destination address, may be routed through different links to reach their destination in a manner invisible to the sender.
A key element in implementing a network using addressed packets is a device called a router (or sometimes a switch) which reads packets' addresses and steers them according to the addresses among the different links joined by the router. For this purpose, the router employs a “routing table” matching packet addresses with ports leading to the different links. The data in the router table maybe manually programmed or may be “learned” using various router heuristics.
Routers may also perform other tasks such as address translation where the packet addresses changed for another packet address, or the management of white or blacklists where certain packets may be blocked, for example, to prevent denial of service attacks where the network is flooded with spurious packets from a given address.
All of these functions of a router require the router to look up packet addresses or other packet features in memory, and to perform these operations repeatedly and rapidly. The capacity of a router, and thus its usefulness, is largely a function of how quickly these memory lookups may be completed.
The memory lookup function may be implemented by a conventional processor reading a table implemented in random access memory. Such memories allow data to be read from identified memory addresses when the address is provided. Finding data with such an architecture requires searching through multiple addresses, a generally time-consuming process. For this reason, high performance routers may use so-called ternary content addressable memories (TCAM) which allow the entire memory to be searched in parallel for the data of interest. These memories substantially reduce the time taken for the memory lookups but are costly and consume considerable power and concomitantly generate greater amounts of heat. Both electrical usage and heat generation can be problems in large data centers.
A possible solution to the problems attendant to rapid memory lookup is the creation of specialized electrical hardware for this purpose. This task, however, is complicated by the variety of different lookup tasks that may be required in a modern router and the need to employ the router in an evolving set of network tasks. For example, currently routers may need to respond to both Internet Protocol (IP) address lookups and local area network (Ethernet-type) lookups. An IP address lookup deals with addresses that have topological significance, that is, different portions of the address represent different networks and subnetworks. For IP address lookups, a tree structure may be preferred as the tree allows successively parsing the network address in a manner that reflects the network topology. In contrast, for Ethernet-type lookups the address will typically have no topological significance, representing simply an arbitrary unique number assigned to each device. In this case, the memory lookups are better implemented using a hash table which encodes no topological information about the addresses stored and allows a simpler lookup operation.
As networks grow more complicated and routers are called upon to execute additional tasks, it is likely that current methods for processing packets will prove sub-optimal and changes to the data structures used by routers during packet processing will be needed. Current method of packet processing may also be sub-optimal for new protocols, extensions to existing protocols, or the introduction of new features for packet processing.